package cn.suchan.jianzhi.q42_sequence;

import java.util.ArrayList;

/**
 * 知识点：和为S的两个数
 * 题目描述
 * 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，
 * 如果有多对数字的和等于S，输出两个数的乘积最小的。
 * 输出描述:
 * 对应每个测试案例，输出两个数，小的先输出。
 *
 * @author suchan
 * @date 2019/06/06
 */
public class Solution {

    /**
     * 直接遍历进行对比
     *
     * @param array
     * @param sum
     * @return
     */
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Integer> resultList = new ArrayList<>();
        if (array.length <= 0 || array == null) {
            return resultList;
        }

        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j < array.length; j++) {
                // 判断和是否为sum
                if (array[i] + array[j] == sum) {
                    if (resultList.isEmpty()) {
                        resultList.add(array[i]);
                        resultList.add(array[j]);
                    } else {
                        int prod1 = resultList.get(0) * resultList.get(1);
                        int prod2 = array[i] * array[j];
                        // 判断乘积大小
                        if (prod1 > prod2) {
                            resultList.set(0, array[i]);
                            resultList.set(1, array[j]);
                        }
                    }
                }
            }
        }

        return resultList;
    }

    /**
     * 由于题目规定必须是递增数列，所以可以使用两个指针，一个指向数列前面，一个指向数列后面
     *
     * @param array
     * @param sum
     * @return
     */
    public ArrayList<Integer> FindNumbersWithSum1(int[] array, int sum) {
        ArrayList<Integer> resultList = new ArrayList<>();
        if (array.length <= 0 || array == null) {
            return resultList;
        }

        int left = 0;
        int right = array.length - 1;

        while (left < right) {
            int tempSum = array[left] + array[right];
            if (tempSum == sum) {
                if (resultList.isEmpty()) {
                    resultList.add(array[left]);
                    resultList.add(array[right]);
                } else {
                    int prod1 = resultList.get(0) * resultList.get(1);
                    int prod2 = array[left] * array[right];
                    // 判断乘积大小
                    if (prod1 > prod2) {
                        resultList.set(0, array[left]);
                        resultList.set(1, array[right]);
                    }
                }
                left++;
                right--;
            } else if (tempSum > sum) {
                right--;
            } else {
                left++;
            }
        }

        return resultList;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};

        Solution solution = new Solution();
        ArrayList<Integer> result = solution.FindNumbersWithSum1(arr, 5);
        System.out.println(result);
    }
}
